#include<stdio.h>
long small[200000],big[200000];
long createm(long n){
    n--;
    long i=1;
    while(n>0){
        n>>=1;
        i<<=1;
    }
    return i;
}
long min(long a,long b){
    if(b==0)return a;
    if(a==0)return b;
    return a>b?b:a;
}
long max(long a,long b){
    if(b==0)return a;
    if(a==0)return b;
    return a>b?a:b;
}
void createBinaryTree(long n,long m){
    long i;
    while(m>0){
        m>>=1;
        n=(n+1)/2;
        for(i=0;i<n;i++){
            small[m+i]=min(small[(m+i)*2],small[(m+i)*2+1]);
            big[m+i]=max(big[(m+i)*2],big[(m+i)*2+1]);
        }
    }    
}
long getMin(long n,long m,long id1,long id2){
    long i1=id1+m,i2=id2+m;
    long left=small[i1],right=small[i2];
    while(i2-i1>1){
        if(((i1&1)==0) && (left>small[i1+1]))left=small[i1+1];
        if(((i2&1)==1) && (right>small[i2-1]))right=small[i2-1];
        
        i1>>=1;
        i2>>=1;
    }
    return min(left,right);
}
void get(long n,long m,long id1,long id2,long *minRet,long *maxRet){
    long i1=id1+m,i2=id2+m;
    long leftMax=big[i1],rightMax=big[i2];
    long leftMin=small[i1],rightMin=small[i2];
    while(i2-i1>1){
        if(((i1&1)==0) && (leftMax<big[i1+1]))leftMax=big[i1+1];
        if(((i2&1)==1) && (rightMax<big[i2-1]))rightMax=big[i2-1];
        
        if(((i1&1)==0) && (leftMin>small[i1+1]))leftMin=small[i1+1];
        if(((i2&1)==1) && (rightMin>small[i2-1]))rightMin=small[i2-1];
        i1>>=1;
        i2>>=1;
    }
    *minRet=min(leftMin,rightMin);
    *maxRet=max(leftMax,rightMax);
}
void input(){
    long i,j,n,m,q,i1,i2,v,leftMax,rightMax,leftMin,rightMin;
    FILE *fp=stdin;//fopen("NKLINEUP.INP","r");
    fscanf(fp,"%ld%ld",&n,&q);
    m=createm(n);
    for(i=0;i<n;i++){
        fscanf(fp,"%ld",&small[i+m]);
        big[i+m]=small[i+m];
    }
    createBinaryTree(n,m);
    for(i=0;i<q;i++){
        fscanf(fp,"%ld%ld",&i1,&i2);
        i1+=m-1;i2+=m-1;
        leftMax=big[i1];rightMax=big[i2];
        leftMin=small[i1];rightMin=small[i2];
        while(i2-i1>1){
            if(((i1&1)==0) && (leftMax<big[i1+1]))leftMax=big[i1+1];
            if(((i2&1)==1) && (rightMax<big[i2-1]))rightMax=big[i2-1];
        
            if(((i1&1)==0) && (leftMin>small[i1+1]))leftMin=small[i1+1];
            if(((i2&1)==1) && (rightMin>small[i2-1]))rightMin=small[i2-1];
            i1>>=1;
            i2>>=1;
        }
        if(i>0)printf("\n");
        printf("%ld",max(leftMax,rightMax)-min(leftMin,rightMin));
    }
}

int main(){
    input();
    return 0;
}
